#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
@ Author: CJK_Monomania
@ Data: 2021-12-21
"""

from typing import *
from pprint import pprint
import numpy as np  # 力扣里面没有
import pandas as pd
import sys   # sys.maxsize---int的最大值

'''
@ 题目: Python
@ 参考链接: 
int最大值: sys.maxsize
float最大值: float('inf')
'''
# Definition for singly-linked list.--链表
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def __init__(self):
        self.result = []
    
    def restoreIpAddresses(self, s: str) -> List[str]:
        if len(s) > 12:
            return []
        self.backtrack(s, startIndex=0, pointNum=0)
        return self.result

    def backtrack(self, s: str, startIndex: int, pointNum: int) -> None:
        if pointNum == 3:
            if self.isValid(s, startIndex,len(s)-1):
                self.result.append(s[:])
            return
        
        for i in range(startIndex,min(startIndex+4,len(s))):
            # [start_index, i]就是被截取的子串
            if self.isValid(s, startIndex,i):
                s = s[:i+1] + '.' + s[i+1:]
                self.backtrack(s,i+2, pointNum+1)
                s = s[i+1:] + s[i+2:]  # 回溯
            else:
                break
    
    def isValid(self, s: str, startIndex: int,endIndex: int) -> bool:
        if startIndex > endIndex:
            return False
        if s[startIndex] == '0' and startIndex != endIndex:
            return False
        if startIndex == endIndex:
            return True
        if not 0 <= int(s[startIndex:endIndex+1]) <= 255:
            return False
        return True
        

# class Solution:
#     def __init__(self):
#         self.result = []

#     def restoreIpAddresses(self, s: str) -> List[str]:
#         '''
#         本质切割问题使用回溯搜索法，本题只能切割三次，所以纵向递归总共四层
#         因为不能重复分割，所以需要start_index来记录下一层递归分割的起始位置
#         添加变量point_num来记录逗号的数量[0,3]
#         '''
#         self.result.clear()
#         if len(s) > 12: return []
#         self.backtracking(s, 0, 0)
#         return self.result

#     def backtracking(self, s: str, start_index: int, point_num: int) -> None:
#         # Base Case
#         if point_num == 3:
#             if self.is_valid(s, start_index, len(s)-1):
#                 self.result.append(s[:])
#             return
#         # 单层递归逻辑
#         for i in range(start_index, len(s)):
#             # [start_index, i]就是被截取的子串
#             if self.is_valid(s, start_index, i):
#                 s = s[:i+1] + '.' + s[i+1:]
#                 self.backtracking(s, i+2, point_num+1)  # 在填入.后，下一子串起始后移2位
#                 s = s[:i+1] + s[i+2:]    # 回溯
#             else:
#                 # 若当前被截取的子串大于255或者大于三位数，直接结束本层循环
#                 break
    
#     def is_valid(self, s: str, start: int, end: int) -> bool:
#         if start > end: return False
#         # 若数字是0开头，不合法
#         if s[start] == '0' and start != end:
#             return False
#         if not 0 <= int(s[start:end+1]) <= 255:
#             return False
#         return True

def main():
    s = "25525511135"
    solu = Solution()
    print(solu.restoreIpAddresses(s))
    s = s[0]
    print(s)


if __name__ == '__main__':
    main()